package com.c2b.algorithm.leetcode.base;

import java.util.Arrays;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/minimum-operations-to-collect-elements/'>收集元素的最少操作次数(Minimum Operations to Collect Elements)</a>
 * <p>给你一个正整数数组 nums 和一个整数 k 。</p>
 * <p>一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。</p>
 * <p>请你返回收集元素 1, 2, ..., k 需要的 最少操作次数 。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [3,1,5,4,2], k = 2
 *      输出：4
 *      解释：4 次操作后，集合中的元素依次添加了 2 ，4 ，5 和 1 。此时集合中包含元素 1 和 2 ，所以答案为 4 。
 *
 * 示例 2：
 *      输入：nums = [3,1,5,4,2], k = 5
 *      输出：5
 *      解释：5 次操作后，集合中的元素依次添加了 2 ，4 ，5 ，1 和 3 。此时集合中包含元素 1 到 5 ，所以答案为 5 。
 *
 * 示例 3：
 *      输入：nums = [3,2,5,3,1], k = 3
 *      输出：4
 *      解释：4 次操作后，集合中的元素依次添加了 1 ，3 ，5 和 2 。此时集合中包含元素 1 到 3  ，所以答案为 4 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= nums.length <= 50</li>
 *      <li>1 <= nums[i] <= nums.length</li>
 *      <li>1 <= k <= nums.length</li>
 *      <li>输入保证你可以收集到元素 1, 2, ..., k 。</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/23 9:58
 */
public class LC2869MinimumOperationsToCollectElements_S {

    static class Solution {

        public int minOperations(List<Integer> nums, int k) {
            // k <= 50,用长整型的64来表示1-k是否出现过
            long target = (2L << k) - 2;
            long currVal = 0;
            for (int i = nums.size() - 1; ; --i) {
                currVal |= (1L << nums.get(i));
                if ((currVal & target) == target) {
                    return nums.size() - i;
                }
            }
        }


        public int minOperations2(List<Integer> nums, int k) {
            boolean[] flags = new boolean[k + 1];
            int count = k;
            int operations = 0;
            for (int i = 0; i < nums.size() && count > 0; i++) {
                Integer integer = nums.get(nums.size() - i - 1);
                if (integer <= k && !flags[integer]) {
                    flags[integer] = true;
                    --count;
                }
                ++operations;
            }
            return operations;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minOperations(Arrays.asList(3, 1, 5, 4, 2), 2));
        System.out.println(solution.minOperations(Arrays.asList(3, 1, 5, 4, 2), 5));
        System.out.println(solution.minOperations(Arrays.asList(3, 2, 5, 3, 1), 3));
    }
}
